#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param: n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        self.rows = n
        self.solution = [-1] * n
        self.ret = []

        self.solve_line(0, list(range(n)))
        return self.ret

    def solve_line(self, row, available_cols):
        # 从第0行开始
        assert row >= 0
        if row > 0:
            assert self.solution[row-1] != -1

        if row == self.rows:
            self.append_solution()


        cols_len = len(available_cols)
        for idx, col in enumerate(available_cols):
            self.clear_row(row)
            if not self.check(row, col):
                continue

            self.solution[row] = col
            new_cols = list(available_cols)
            del new_cols[idx]
            self.solve_line(row+1, new_cols)

    def check(self, row, col):
        if row == 0:
            return True

        def check_one_row(r1, c1, r2, c2):
            if r1 == r2 or c1 == c2:
                return False

            slop = (r1 - r2) / (c1 - c2)
            if slop == -1 or slop == 1:
                return False

            return True

        # 检查所有之前的行
        for r in range(row):
            if not check_one_row(r, self.solution[r], row, col):
                return False

        return True

    def clear_row(self, row):
        self.solution[row] = -1

    def append_solution(self):
        # self.ret.append(list(self.solution))
        line = ['.'] * self.rows
        # solution_matrix = [line] * self.rows
        solution_matrix = [list(line) for i in range(self.rows)]
        print(solution_matrix)
        print(self.solution)
        for row, col in enumerate(self.solution):
            solution_matrix[row][col] = "Q"
        # print(solution_matrix)
        solution = ["".join(line) for line in solution_matrix]
        self.ret.append(solution)


def main():
    from pprint import pprint
    print("start main")
    s = Solution()
    ret = s.solveNQueens(4)
    # print(len(ret))
    pprint(ret)

if __name__ == "__main__":
    main()
